// 1、魔力台阶 100分

// 科科最近在修炼魔法，一日他来到魔法城堡，城堡里有一个长长的台阶，而台阶的最终点便是魔法奥秘。

// 这是一个魔力台阶，每个台阶都有一个魔力值，魔力值代表下一步科科最大可以跨越的台阶数。

// 科科当前处在第1级台阶上，但是科科的体力有限，最多只能跨越K次。科科现在拜托你帮他计算下他能否拿到魔法奥秘。

// 如果能够拿到返回最少跨越的次数，拿不到则返回-1。

// 解答要求

// 时间限制:C/C++ 1000ms,其他语言:2000ms

// 内存限制:C/C++ 256MB,其他语言:512MB

// 输入

// 台阶长度n (1<=n<=10^5)

// 台阶魔力值，[M1, M2….. Mn]由一个长度为n的数组表示，代表1~n级台阶的魔力值。(0<=Mi<=10^5)

// 最大的跨越次数K(1<=k<=10^5)

// 输出

// 输出一个整数，拿到魔法奥秘最少需要跨越的次数，如果拿不到，返回-1。


// 算法思想
//     此题和 LeetCode 45 题非常像，只是在次数判定时候，达到体力上限直接返回 - 1 ；

class Solution {
public:
    int jump(vector<int>& nums) {
    	int res = 0;
    	int start = 0;	// 起跳开始的台阶
    	int end = 1;	// 起跳结束的台阶

    	// 跳到的最远位置不能到达末尾
    	while(end < nums.size()) {
    		int maxPos = 0;

    		// 在起跳范围内，找出能跳到的最远位置
    		for(int i = start; i < end; ++i) {
    			maxPos = max(maxPos, i + nums[i]);
    		}
    		start = end;		// 下次起跳范围开始位置
    		end = maxPos + 1;	// 下次起跳范围结束位置
    		res++;
            if(res > k)
                return -1;
    	}
    	return res;
    }
};